home *** CD-ROM | disk | FTP | other *** search
/ Internet Surfer: Getting Started / Internet Surfer - Getting Started (Wayzata Technology)(7231)(1995).bin / pc / textfile / mac_faqs / linear_p < prev    next >
Internet Message Format  |  1995-01-30  |  38KB

  1. Xref: bloom-picayune.mit.edu news.answers:4542 sci.math.num-analysis:6341
  2. Path: bloom-picayune.mit.edu!enterpoop.mit.edu!news.media.mit.edu!micro-heart-of-gold.mit.edu!rutgers!sun-barr!cs.utexas.edu!uunet!timbuk.cray.com!walter.cray.com!jwg
  3. From: jwg@cray.com (John W. Gregory)
  4. Newsgroups: news.answers,sci.math.num-analysis
  5. Subject: Linear Programming FAQ
  6. Summary: A List of Frequently Asked Questions about Linear Programming
  7. Keywords: FAQ, LP, Linear Programming
  8. Message-ID: <linear-programming-faq-1-724103080@cray.com>
  9. Date: 11 Dec 92 19:44:49 GMT
  10. Expires: 02/14/93
  11. Reply-To: jwg@cray.com (John W. Gregory)
  12. Followup-To: sci.math.num-analysis
  13. Organization: Cray Research, Inc., Eagan MN USA
  14. Lines: 707
  15. Approved: news-answers-request@MIT.Edu
  16. Originator: jwg@ceres
  17. Nntp-Posting-Host: ceres.cray.com
  18.  
  19. Posted-By: auto-faq 2.4
  20. Archive-name: linear-programming-faq
  21. Last-modified: 1992/12/11
  22.  
  23.  
  24.            Linear Programming - Frequently Asked Questions List
  25.                                  (lp_faq)
  26.                    Most recent update: December 11, 1992                 
  27.  
  28. --------------------------------------------------------------------------
  29.  
  30. 0.  "What's in this FAQ?"
  31.  
  32. A:  Table of Contents
  33.     0.  "What's in this FAQ?"  (Oh no! Is this a recursion?)
  34.     1.  "What is Linear Programming?"
  35.     2.  "Where is there a good code, preferably public domain, to solve 
  36.          Linear Programming problems?"
  37.     3.  "Oh, and we also want to solve it as an integer program. I think
  38.          there will be only a few thousand variables or so."
  39.     4.  "I've written my own optimization code.  Where are some test models?"
  40.     5.  "What is MPS format?"
  41.     6.  "What software is there for non-linear optimization?"
  42.     7.  "What references are there in this field?"
  43.     8.  "Just a quick question..."
  44.     9.  "Who maintains this FAQ list?"
  45.  
  46. --------------------------------------------------------------------------
  47.  
  48. 1.  "What is Linear Programming?"
  49.  
  50. A:  A linear program (LP) is a problem that can be put into the form
  51.  
  52.     minimize   cx
  53.     subject to Ax=b
  54.                 x>=0
  55.  
  56. where x is a vector to be solved for, A is a matrix of known coefficients, 
  57. and c and b are vectors  of known coefficients.  All these entities must 
  58. have consistent dimensions, of course, and you can add "transpose" symbols
  59. to taste.  The matrix A is generally not square, hence you don't solve an
  60. LP by just inverting A.  Usually A has more columns than rows, so  Ax=b  
  61. is therefore underdetermined, leaving great latitude in the choice of x 
  62. with which to minimize cx.
  63.  
  64. Other formulations can be used in this framework.  For instance, if you 
  65. want to maximize instead of minimize, multiply the c vector by -1.  If 
  66. you have constraints that are inequalities rather than equations, you 
  67. can introduce one new variable (a "slack") for each inequality and treat 
  68. the augmented row of the matrix as an equation.  LP codes will often 
  69. take care of such "bookkeeping" for you.
  70.  
  71. LP problems are usually solved by a technique known as the Simplex Method, 
  72. developed in the 1940's and after.  Briefly stated, this method works by 
  73. taking a sequence of square submatrices of A and solving for x, in such a 
  74. way that successive solutions always improve, until a point is reached 
  75. where improvement is no longer possible.  A family of LP algorithms known 
  76. as Interior Point methods has been developed starting in the 1980's, that 
  77. can be faster for many (but so far not all) problems.  Such methods are
  78. characterized by constructing a sequence of trial solutions that go 
  79. through the interior of the solution space, in contrast to the Simplex
  80. Method which stays on the boundary and examines only the corners (vertices).
  81.  
  82. LP has a variety of uses, in such areas as petroleum, finance, transportation, 
  83. forestry, and military.
  84.  
  85. The word "Programming" is used here in the sense of "planning"; the
  86. necessary relationship to computer programming was incidental to the 
  87. choice of name.  Hence the phrase "LP program" to refer to a piece of 
  88. software is not a redundancy, although I tend to use the term "code" 
  89. instead to avoid the possible ambiguity.
  90.  
  91. --------------------------------------------------------------------------
  92.  
  93. 2.  "Where is there a good code, preferably public domain, to solve 
  94. Linear Programming problems?"
  95.  
  96. A:  It depends on the difficulty of your models.  LP technology and
  97. computer technology have both made such great leaps that models that 
  98. were previously considered "large" are now routinely solved.  Nowadays, 
  99. with good commercial software, models with a few thousand constraints 
  100. and several thousand variables can be tackled with a PC.  Workstations 
  101. can often handle models with variables in the tens of thousands, or even 
  102. greater.  It's hard to be specific about sizes and speed, a priori, due 
  103. to the wide variation in things like model structure and variation in 
  104. factorizing the basis matrices.
  105.  
  106. There is a recently released public domain code, written in C, called 
  107. "lp_solve" that is available on Usenet in the "comp.sources.reviewed" 
  108. newsgroup.  Its author (Michel Berkelaar, email at michel@es.ele.tue.nl) 
  109. claims to have solved models with up to 30,000 variables and 50,000 
  110. constraints.  My own experience with this code is not quite so uniformly 
  111. optimistic (new users of LP are sometimes shocked to learn that just
  112. because a given code has solved a model of a given dimension, it may not
  113. be able to solve all models of the same size).  Still, for someone who 
  114. isn't sure just what kind of LP code is needed, it represents a very 
  115. reasonable first try, and the price is certainly right.  The code is 
  116. archived at anonymous ftp site "ftp.uu.net", in directory 
  117.     "/usenet/comp.sources.reviewed/volume02/lp_solve".  
  118. It consists of three files, part00.Z, part01.Z and part02.Z.  You should 
  119. download them in binary mode, and use the `uncompress` utility to expand 
  120. them to normal ASCII format.  The file called part00 contains reviewers'
  121. comments, and the other two files can be unpacked by removing the first
  122. 9 lines and executing the files as shell scripts (e.g., `sh part01`).  
  123. Then follow the instructions in the README and INSTALL files.
  124.  
  125. For DOS/PC users, Prof. Timo Salmi at the University of Vaasa in Finland 
  126. offers a code called "tslin".  You should be able to access it by ftp at 
  127. garbo.uwasa.fi in directory /pc/ts (the current file name is tslin33b.zip, 
  128. apparently using ZIP compression), or else I suggest contacting Prof. 
  129. Salmi at ts@uwasa.fi.
  130.  
  131. The consensus is that the LP code published in Numerical Recipes is not at 
  132. all strong, and should be avoided for heavy-duty use.  If your requirement 
  133. is for a solver that can handle 100-variable models, it might be okay.
  134.  
  135. There is an ACM TOMS routine for LP, #552, available from the netlib server,
  136. in directory /netlib/toms.  See the section on test models for detail on 
  137. how to use this server.
  138.  
  139. If you have access to one of the commercial math libraries, such as IMSL or 
  140. NAG, you may be able to use an LP routine from there.
  141.  
  142. If your models prove to be too difficult for free software to handle, 
  143. then you can consider acquiring a commercial LP code.  There are dozens 
  144. of such codes on the market. I have my own opinions, but for reasons of 
  145. space, generality and fairness, I will not attempt even to list the codes 
  146. I know of here.  Instead I refer you to the annual survey of LP software 
  147. published in "OR/MS Today", a joint publication of ORSA (Operations 
  148. Research Society of America) and TIMS (The Institute of Management 
  149. Science).  I think it's likely that you can find a copy of the June, 1992 
  150. issue, either through a library, or by contacting a member of these two 
  151. organizations (most universities probably have several members among the 
  152. faculty and student body).  The survey lists almost fifty actively marketed 
  153. products.  This publication also carries advertisements for many of these 
  154. products, which may give you additional information to help make a decision.
  155.  
  156. There are many considerations in selecting an LP code.  Speed is important, 
  157. but LP is complex enough that different codes go faster on different models; 
  158. you won't find a "Consumer Reports" article  8v)  to say with certainty which 
  159. code is THE fastest.  I usually suggest getting benchmark results for your 
  160. particular type of model if speed is paramount to you.  Benchmarking may 
  161. also help determine whether a given code has sufficient numerical stability 
  162. for your kind of models.
  163.  
  164. Other questions you should answer: Can you use a stand-alone code, or do 
  165. you need a code that can be used as a callable library, or do you require 
  166. source code?  Do you want the flexibility of a code that runs on many 
  167. platforms and/or operating systems, or do you want code that's tuned to 
  168. your particular hardware architecture (in which case your hardware vendor 
  169. may have suggestions)?  Is the choice of algorithm (Simplex, Interior 
  170. Point) important to you?  Do you need an interface to a spreadsheet 
  171. code?  Is the purchase price an overriding concern?  Is the software 
  172. offered at an academic discount (assuming you are at a university)?  How 
  173. much hotline support do you think you'll need?  
  174.  
  175. It may not always be true that "you get what you pay for," but it is rare 
  176. that you get more than you pay for.  8v)   There is usually a large 
  177. difference in LP codes, in performance (speed, numerical stability, 
  178. adaptability to computer architectures) and features, as you climb the 
  179. price scale.  If a code seems overpriced to you, you may not yet 
  180. understand all of its features.
  181.  
  182. --------------------------------------------------------------------------
  183.  
  184. 3.  "Oh, and we also want to solve it as an integer program. I think
  185. there will be only a few thousand variables or so."
  186.  
  187. A:  Hmmmm.  You want
  188.     - Nontrivial model size
  189.     - Integer solutions
  190.     - Public domain code
  191. Pick one or maybe two of the above.  You can't have all three.  8v)
  192.  
  193. Integer LP models are ones where the answers must not take fractional 
  194. values.  It may not be obvious that this is a VERY much harder problem 
  195. than ordinary LP, but it is nonetheless true.  The buzzword is "NP-
  196. Completeness", the definition of which is beyond the scope of this 
  197. document but means in essence that in the worst case the amount of
  198. time to solve a family of related problems goes up exponentially
  199. as the size of the problem grows.  
  200.  
  201. Integer models may be ones where only some of the variables are to be 
  202. integer and others may be real-valued (termed "Mixed Integer LP" or 
  203. MILP, or "Mixed Integer Programming" or MIP), or they may be ones where 
  204. all the variables must be integral (termed "Integer LP" or ILP).  The 
  205. class of ILP is often further subdivided into problems where the only 
  206. legal values are {0,1} ("Binary" or "Zero-One" ILP), and general integer 
  207. problems.  For the sake of generality, the Integer LP problem will be 
  208. referred to here as MIP, since the other classes can be viewed as special 
  209. cases of MIP.
  210.  
  211. You should be prepared to solve far smaller MIP models than the 
  212. corresponding LP model, given a certain amount of time you wish to 
  213. allow (unless you and your model happen to be very lucky). There exist 
  214. models that are considered challenging, with mere hundreds of variables. 
  215. Conversely, some models with tens of thousands of variables solve 
  216. readily.  It all depends, and the best explanations of "why" always
  217. seem to happen after the fact.  8v)
  218.  
  219. One exception to this gloomy outlook is that there are certain models
  220. whose LP solution always turns out to be integer.  Best known of these
  221. are the so-called Transportation Problem, Assignment Problem, and
  222. Network-Flow Problem.  It turns out that these problems are best solved 
  223. by specialized routines that take major shortcuts in the Simplex Method, 
  224. and as a result are relatively quick running.  See the section on 
  225. references for a book by Kennington and Helgason, which contains some 
  226. source code for Netflo.  Netflo is available by anonymous ftp at 
  227. dimacs.rutgers.edu, in directory /pub/netflow/mincost/solver-1, but
  228. I don't know the copyright situation (I used to think you had to buy
  229. the book to get the code).
  230.  
  231. People are sometimes surprised to learn that MIP problems are solved 
  232. using floating point arithmetic.  Although various algorithms for MIP 
  233. have been studied, most if not all available general purpose large-scale 
  234. LP codes use a method called "Branch and Bound" to try to find an optimal 
  235. solution.  In a nutshell, B&B solves MIP by solving a sequence of related 
  236. LP models.  Good codes for MIP distinguish themselves more by solving 
  237. shorter sequences of LP's, than by solving the individual LP's faster.  
  238. Even moreso than with regular LP, a costly commercial code may prove its 
  239. value to you if your MIP model is difficult.
  240.  
  241. As a point of interest, the Simplex Method currently retains an advantage 
  242. over the newer Interior Point methods for solving these sequences of LP's.
  243.  
  244. The public domain code "lp_solve", mentioned earlier, accepts MIP models,
  245. as do a large proportion of the commercial LP codes in the OR/MS Today 
  246. survey.  I have seen mention made of algorithm 333 in the Collected 
  247. Algorithms from CACM, though I'd be surprised if it was robust enough 
  248. to solve large models.  
  249.  
  250. The better MIP codes have numerous parameters and options to give the user 
  251. control over the solution strategy. Most have the capability of stopping 
  252. before an optimum is proved, printing the best answer obtained so far.  
  253. For many MIP models, stopping early is a practical necessity. Fortunately, 
  254. a solution that has been proved by the algorithm to be within, say, 1% of 
  255. optimality often turns out to be the true optimum, and the bulk of the 
  256. computation time is spent proving the optimality. For many modeling 
  257. situations, a near-optimal solution is acceptable anyway.
  258.  
  259. Once one accepts that large MIP models are not typically solved to a
  260. proved optimal solution, that opens up a broad area of approximate 
  261. methods, probabilistic methods and heuristics, as well as modifications
  262. to B&B.  Claims have been made for Genetic Algorithms and Simulated 
  263. Annealing, though (IMHO) these successes have been problem dependent 
  264. and difficult to generalize.  (A reference for GA is David Goldberg, 
  265. "Genetic Algorithms in Machine Learning.")  
  266.  
  267. Whatever the solution method you choose, when trying to solve a difficult 
  268. MIP model, it is usually crucial to understand the workings of the physical 
  269. system (or whatever) you are modeling, and try to find some insight that 
  270. will assist your chosen algorithm to work better.  A related observation 
  271. is that the way you formulate your model can be as important as the actual 
  272. choice of solver.  You should consider getting some assistance if this 
  273. is your first time trying to solve a large (>100 variable) problem.
  274.  
  275. --------------------------------------------------------------------------
  276.  
  277. 4.  "I've written my own optimization code.  Where are some test models?"
  278.  
  279. A:  In light of the comments above, I hope your aims are fairly modest,
  280. for there are already a lot of good codes out there.  I hope your LP 
  281. code makes use of sparse matrix techniques, rather than using a tableau
  282. form of the Simplex method, because the latter usually ends up being
  283. numerically unstable and very slow.
  284.  
  285. If you want to try out your code on some real-world LP models, there is 
  286. a very nice collection of small-to-medium-size ones on netlib.  If you
  287. have ftp access, you can try "ftp research.att.com", using "netlib"
  288. as the Name, and your email address as the password. Do a "cd lp/data"
  289. and look around. There should be a "readme" file, which you would 
  290. want to look at first.  Alternatively, you can reach an e-mail
  291. server via "netlib@ornl.gov", to which you can send a message saying
  292. "send index from lp/data"; follow the instructions you receive.
  293.  
  294. The Netlib LP files (after you uncompress them) are in a format called 
  295. MPS, which is described in another section of this document.
  296.  
  297. There is a collection of MIP models, housed at Rice University.  Send
  298. an email message containing "send catalog" to softlib@rice.edu, to get
  299. started.
  300.  
  301. There is a collection of network-flow codes and models at DIMACS (Rutgers
  302. University).  Use anonymous FTP at dimacs.rutgers.edu.  Start looking in
  303. /pub/netflow.  Another network generator is called NETGEN and is available
  304. on netlib (lp/generators).
  305.  
  306. John Beasley has posted information on his OR-Lib, which contains various
  307. optimization test problems.  Send e-mail to umtsk99@vaxa.cc.imperial.ac.uk
  308. to get started.  Or have a look in the Journal of the Operational Research
  309. Society, Volume 41, Number 11, Pages 1069-72.
  310.  
  311. There are various test sets for NLP (Non-Linear Programming).  Among
  312. those I've seen mentioned are
  313.   - ACM TOMS (Transactions on Mathematical Software), V13 No3 P272
  314.   - publications (listed in another section of this list) by Schittkowski; 
  315.     Hock & Schittkowski;  Floudas & Pardalos; Torn; Hughes & Grawiog.
  316. Many of the other references also contain various problems that you
  317. could use to test a code.
  318.  
  319. The modeling language GAMS comes with about 100 test models, which
  320. you might be able to test your code with.
  321.  
  322. --------------------------------------------------------------------------
  323.  
  324. 5.  "What is MPS format?"
  325.  
  326. A:  MPS format was named after an early IBM LP product and has emerged 
  327. as a de facto standard ASCII medium among most of the various commercial 
  328. LP codes.  You will need to write your own reader routine for this, but 
  329. it's not too hard. The main things to know about MPS format are that it 
  330. is column oriented (as opposed to entering the model as equations), and 
  331. everything (variables, rows, etc.) gets a name.  MPS format is described 
  332. in more detail in Murtagh's book, referenced in another section.  Here 
  333. is a little sample model, explained in more detail below:
  334.  
  335. NAME          METALS   
  336. ROWS
  337.   N VALUE
  338.   E YIELD
  339.   L FE
  340.   L MN
  341.   L CU
  342.   L MG
  343.   G AL
  344.   L SI
  345. COLUMNS
  346.     BIN1      VALUE       0.03         YIELD           1.
  347.     BIN1      FE          0.15         CU             .03
  348.     BIN1      MN          0.02         MG             .02
  349.     BIN1      AL          0.7          SI             .02
  350.     BIN2      VALUE       0.08         YIELD           1.
  351.     BIN2      FE           .04         CU             .05
  352.     BIN2      MN           .04         MG             .03
  353.     BIN2      AL           .75         SI             .06
  354.     BIN3      VALUE       0.17         YIELD         1.
  355.     BIN3      FE           .02         CU             .08
  356.     BIN3      MN           .01         AL             .8
  357.     BIN3      SI           .08
  358.     BIN4      VALUE       0.12         YIELD         1.
  359.     BIN4      FE           .04         CU             .02
  360.     BIN4      MN           .02         AL             .75
  361.     BIN4      SI          0.12
  362.     BIN5      VALUE       0.15         YIELD         1.
  363.     BIN5      FE           .02         CU             .06
  364.     BIN5      MN           .02         MG             .01
  365.     BIN5      SI           .02         AL             .8
  366.     ALUM      VALUE       0.21         YIELD         1.
  367.     ALUM      FE           .01         CU             .01
  368.     ALUM      AL           .97         SI             .01
  369.     SILCON    VALUE       0.38         YIELD         1.
  370.     SILCON    FE           .03         SI             .97
  371. RHS
  372.     ALOY1     YIELD        2000.       FE              60.
  373.     ALOY1     CU            100.       MN              40.
  374.     ALOY1     MG             30.       AL            1500.
  375.     ALOY1     SI            300.
  376. BOUNDS
  377.  UP PROD1     BIN1            200.00
  378.  UP PROD1     BIN2            750.00
  379.  LO PROD1     BIN3            400.00
  380.  UP PROD1     BIN3            800.00
  381.  LO PROD1     BIN4            100.00
  382.  UP PROD1     BIN4            700.00
  383.  UP PROD1     BIN5           1500.00
  384. ENDATA
  385.  
  386.  
  387. MPS is an old format, so it is set up as though you were using
  388. punch cards, and is not free format. Fields start in column 1,
  389. 5, 15, 25, 40 and 50.  Sections of an MPS file are marked by
  390. so-called header cards, which are distinguished by their starting
  391. in column 1.  Although it is typical to use upper-case throughout
  392. the file (like I said, MPS has long historical roots), many 
  393. MPS-readers will accept mixed-case for anything except the
  394. header cards, and some allow mixed-case anywhere.
  395.  
  396. The NAME card can be anything you want.  The ROWS section defines 
  397. the names of all the constraints; entries in column 2 or 3 are E 
  398. for equality rows, L for less-than ( <= ) rows, G for greater-than  
  399. ( >= ) rows, and N for non- constraining rows (the first of which 
  400. would be interpreted as the objective function).
  401.  
  402. The largest part of the file is in the COLUMNS section, which is 
  403. the place where the entries of the A-matrix are put.  All entries 
  404. for a given column must be placed consecutively, although within 
  405. a column the order of the entries (rows) is irrelevant. Rows not 
  406. mentioned for a column are assumed to have a coefficient of zero.
  407.  
  408. The RHS section allows one or more right-hand-side vectors to be 
  409. defined; most people don't bother having more than one.  In the
  410. above example, its name is ALOY1, and has non-zero values in all
  411. 7 of the constraint rows of the problem.  Rows not mentioned are 
  412. assumed to have a right-hand-side of zero.
  413.  
  414. The optional BOUNDS section lets you put lower and upper bounds on 
  415. individual variables (no * wildcards, unfortunately), instead of 
  416. having to define extra rows in the matrix.  All the bounds that have 
  417. a given name in column 5 are taken together as a set.  Variables 
  418. not mentioned in a BOUNDS set are taken to be non-negative.  There 
  419. is another optional section called RANGES that I won't go into 
  420. here. The final card must be the ENDATA, and yes, it is spelled 
  421. funny.
  422.  
  423. For comparison, here is the same model written out in equation 
  424. format.
  425.  
  426. Minimize
  427.  VALUE: 0.03 BIN1 + 0.08 BIN2 + 0.17 BIN3 + 0.12 BIN4 + 0.15 BIN5 
  428.  + 0.21 ALUM + 0.38 SILCON
  429. Subject To
  430.  YIELD: BIN1 + BIN2 + BIN3 + BIN4 + BIN5 + ALUM + SILCON  = 2000
  431.  FE:    0.15 BIN1 + 0.04 BIN2 + 0.02 BIN3 + 0.04 BIN4 + 0.02 BIN5 
  432.         + 0.01 ALUM + 0.03 SILCON <= 60
  433.  MN:    0.02 BIN1 + 0.04 BIN2 + 0.01 BIN3 + 0.02 BIN4 + 0.02 BIN5 
  434.         <= 40
  435.  CU:    0.03 BIN1 + 0.05 BIN2 + 0.08 BIN3 + 0.02 BIN4 + 0.06 BIN5 
  436.         + 0.01 ALUM <= 100
  437.  MG:    0.02 BIN1 + 0.03 BIN2 + 0.01 BIN5 <= 30
  438.  AL:    0.7 BIN1 + 0.75 BIN2 + 0.8 BIN3 + 0.75 BIN4 + 0.8 BIN5 
  439.         + 0.97 ALUM >= 1500
  440.  SI:    0.02 BIN1 + 0.06 BIN2 + 0.08 BIN3 + 0.12 BIN4 + 0.02 BIN5 
  441.         + 0.01 ALUM + 0.97 SILCON <= 300
  442. and
  443.         0 <= BIN1 <= 200
  444.         0 <= BIN2 <= 750
  445.         400 <= BIN3 <= 800
  446.         100 <= BIN4 <= 700
  447.         0 <= BIN5 <= 1500
  448.  
  449. --------------------------------------------------------------------------
  450.  
  451. 6.  "What software is there for non-linear optimization?"
  452.  
  453. A:  I don't claim as much expertise in this area, but the question is 
  454. frequent enough to be worth addressing.  If I get enough feedback, this 
  455. section might grow large enough to need to be split off as a separate 
  456. FAQ list.
  457.  
  458. It's unrealistic to expect to find one general NLP code that's going to
  459. work for every kind of nonlinear model.  Instead, you should try to find 
  460. a code that fits the problem you are solving.  Nonlinear solution techniques 
  461. can be divided into various categories, such as unconstrained, linearly 
  462. constrained, convexly constrained, or general.  If your problem doesn't
  463. fit in any category except "general", or you insist on a proven optimal
  464. solution (except when there no chance of multiple local minima), you should 
  465. be prepared to have to use a method that boils down to exhaustive search, 
  466. i.e., you have an intractable problem.  See the comments in the MIP section 
  467. on Simulated Annealing and Genetic Algorithms.
  468.  
  469. Several of the commercial LP codes referenced above have specialized 
  470. routines, particularly for Quadratic Programming (QP, linear constraints 
  471. with a quadratic objective function).  Many nonlinear problems can be
  472. solved (or at least confronted) by application of a sequence of LP or 
  473. QP approximations.
  474.  
  475. There is an ACM TOMS routine for QP, #587, available from the netlib server,
  476. in directory /netlib/toms.  See the section on test models for detail on 
  477. how to use this server.
  478.  
  479. There is a directory, /netlib/opt, on the netlib server containing a 
  480. collection of optimization routines.  At my last check, I saw 
  481. - "praxis" (unconstrained optimization, without requiring derivatives)  
  482. - "tn" (Newton method for unconstrained or simple-bound optimization)
  483. - "ve08" (optimization of unconstrained separable function).
  484. - "simann" (unconstrained optimization using Simulated Annealing)
  485. - "vfsr" (constrained optimization using Simulated Annealing)
  486. Again, see the section on test models for detail on how to use this server.
  487.  
  488. Here is a summary of codes mentioned in newsgroups in the past year, not 
  489. sorted into categories.
  490.  
  491. - MINOS - Stanford University, Office of Technology Licensing, 415-723-0651.
  492.   This code is often used by researchers as a "benchmark" for others to 
  493.   compare with.
  494. - NPSOL - Stanford University, Office of Technology Licensing, 415-723-0651.
  495. - QPSOL - Stanford University, Office of Technology Licensing, 415-723-0651.
  496. - NAG Library routine E04UCF.
  497. - IMSL routine UMINF and UMIDH.
  498. - Harwell Library routine VF04.
  499. - Hooke and Jeeves algorithm - reference?
  500. - MINPAK I and II - Contact Steve Wright, wright@mcs.anl.gov
  501. - GENOCOP - Genetic algorithm, Zbigniew Michalewicz, zbyszek@mosaic.uncc.edu
  502.   said to be available by ftp at unccsun.uncc.edu (152.15.10.88).
  503. - DFPMIN - Numerical Recipes  (Davidon-Fletcher-Powell)
  504. - Amoeba - Numerical Recipes
  505. - Brent's Method - Numerical Recipes
  506. - FSQP -  Contact Andre Tits, andre@src.umd.edu.  Said to be free of charge 
  507.   to academic users.
  508. - CONMIN - Vanderplaats and Associates, Goleta CA
  509. - NOVA - DOT Products, Houston TX
  510. - GRG2 - Leon Lasdon, University of Texas, Austin TX
  511. - GINO - LINDO Systems, Chicago, IL
  512.  
  513. --------------------------------------------------------------------------
  514.  
  515. 7.  "What references are there in this field?"
  516.  
  517. A:  Too many to count.  Here are a few that I like or have been 
  518. recommended on the net.  I have *not* reviewed them all.
  519.  
  520. General reference  [1]
  521. - Nemhauser, Rinnooy Kan, & Todd, eds, Optimization, North-Holland, 1989.
  522.   (Very broad-reaching, with large bibliography.  Good reference; it's
  523.   the place I tend to look first.  Tough sledding for beginners.)
  524.  
  525. LP 
  526. - Chvatal, Linear Programming, Freeman, 1983.  (I find it hard to whole-
  527.   heartedly recommend any one LP textbook, but this is one I'd probably use
  528.   in teaching an undergraduate course.)
  529. - Hughes & Grawiog, Linear Programming: An Emphasis on Decision Making,
  530.   Addison-Wesley, 1973.  
  531. - Luenberger, Introduction to Linear and Nonlinear Programming, Addison 
  532.   Wesley, 1984.  (Updated version of an old standby.)
  533. - Murtagh, B., Advanced Linear Programming, McGraw-Hill, 1981.  (Good one
  534.   after you've read an introductory text.)
  535. - Schrijver, Theory of Linear and Integer Programming, Wiley.
  536. - Williams, H.P., Model Building in Mathematical Programming, Wiley 1985.
  537.   (Little on algorithms, but excellent for learning what makes a good model.)
  538.  
  539. Interior Point LP
  540. - Marsten, et al., "Interior point methods for linear programming", 
  541.   Interfaces, pp 105-116, July-August 1990.  (Introductory article, written 
  542.   by authors of a good commercial code.)
  543. - Marsten, et al., article to appear in ORSA Journal on Computing, 1993.
  544.   (The latest results; a tech report version may be available sooner.)
  545. - Wright, M., "Interior methods for constrained optimization", Acta Mathematica,
  546.   Cambridge University Press, 1992.  (Survey article.)
  547. There is also a bibliography (with over 1000 entries!?!) obtainable by 
  548. mailing to "netlib@ornl.gov" and saying "send intbib.bib from bib".
  549.  
  550. Nonlinear Programming  (can someone help classify these more usefully?)
  551. - Bazaraa & Shetty, Nonlinear Programming, Theory & Applications.
  552. - Coleman & Li, Large Scale Numerical Optimization, SIAM Books.
  553. - Dennis & Schnabel, Numerical Methods for Unconstrained Optimization
  554.   and Nonlinear Equations, Prentice Hall, 1983.
  555. - Fiacco & McCormick, Sequential Unconstrained Minimization Techniques,
  556.   SIAM Books.  (An old standby, given new life by the interior point
  557.   LP methods.)
  558. - Fletcher, R., Practical Methods of Optimization, Wiley 1987.  (Good
  559.   reference for Quadratic Programming, among other things.)
  560. - Floudas & Pardalos, A collection of test problems for constrained
  561.   optimization algorithms, Springer-Verlag, 1990.
  562. - Gill, Murray & Wright, Practical Optimization, Academic Press, 1981.
  563.   (An instant NLP classic when it was published.)
  564. - Hock & Schittkowski, Test Examples for Nonlinear Programming Codes,
  565.   Springer-Verlag, 1981.
  566. - Kahaner, Moler & Nash, Numerical Methods and Software, Prentice-Hall.
  567. - More, "Numerical Solution of Bound Constrained Problems", in Computational
  568.   Techniques & Applications, CTAC-87, Noye & Fletcher, eds, North-Holland,
  569.   29-37,  1988.
  570. - More & Toraldo, Algorithms for Bound Constrained Quadratic Programming
  571.   Problems, Numerische Mathematik 55, 377-400, 1989.
  572. - Schittkowski, Nonlinear Programming Codes, Springer-Verlag, 1980.
  573. - Torn & Zilinskas, Global Optimization, Springer-Verlag, 1989.
  574.  
  575. Other publications
  576. - Forsythe, Malcolm & Moler, Computer Methods for Mathematical Computations, 
  577.   Prentice-Hall.
  578. -Hansen, Global Optimization Using Interval Analysis, Marcel Dekker, 1991(?).
  579.   (I'd be interested if anyone has any opinions on this one.)
  580. - Kennington & Helgason, Algorithms for Network Programming, Wiley, 1980.
  581.   (A special case of LP.)
  582. - Kirkpatrick, Gelatt & Vecchi, Optimization by Simulated Annealing,
  583.   Science, 220 (4598) 671-680, 1983.
  584. - Press, Flannery, Teukolsky & Vetterling , Numerical Recipes, Cambridge,
  585.   1986.    (Comment: use with care.)
  586.  
  587.  
  588. --------------------------------------------------------------------------
  589.  
  590. 8.  "Just a quick question..."
  591.  
  592. Q:  What is a matrix generator?
  593. A:  This is a code that creates input for an LP (or MIP, or NLP) code, 
  594.     using a more natural input than MPS format.  There are no free ones.  
  595.     Big names in this area are GAMS (Scientific Press), LINGO (LINDO 
  596.     Systems), and AMPL (information is in netlib/opt on the Netlib server).
  597.     These products have links to various solvers (commercial and otherwise).
  598. Q:  How do I diagnose an infeasible LP model?
  599. A:  A model is infeasible if the constraints are inconsistent, i.e., if
  600.     no feasible solution can be constructed.  It's often difficult to track 
  601.     this down.  The cure may even be ambiguous: is it that some demand 
  602.     was set too high, or a supply set too low?  A useful technique is Goal 
  603.     Programming, one variant of which is to include two explicit slack 
  604.     variables (positive and negative) with huge cost coefficients, in each 
  605.     constraint.  The revised model is guaranteed to have a solution, and you 
  606.     can look at which rows have slacks that are included in the "optimal" 
  607.     solution.  By the way, I recommend a Goal Programming philosophy even if 
  608.     you aren't having trouble with feasibility; "come on, you could probably 
  609.     violate this constraint for a price."
  610. Q:  I want to know specifically which constraints contradict each other.
  611. A:  This may not be a well posed problem.  If by this you mean you want to 
  612.     find the minimal set of constraints that should be removed to restore 
  613.     feasibility, this can be modeled as an Integer LP (which means, it's 
  614.     potentially a hard problem). Start with a Goal Programming approach as 
  615.     outlined above, and introduce some 0-1 variables to turn the slacks off 
  616.     or on.  Then minimize on the sum of these 0-1 variables.
  617. Q:  I just want to know whether or not there *exists* a feasible solution.
  618. A:  Finding out if a model has a feasible solution is essentially as hard 
  619.     as finding the optimal solution (within a factor of 2 on average, in 
  620.     terms of effort in the Simplex Method).  There are no shortcuts in 
  621.     general, unless you know something useful about your model's structure.
  622. Q:  I have an LP, except it's got several objective functions.  Help!
  623. A:  This is indeed a difficult class of model.  Fundamental to it is that
  624.     there may be no unique solution.  Approaches that have worked are
  625.     Goal Programming (treat the objectives as constraints with costed
  626.     slacks), Pareto preference analysis, and forming a composite objective
  627.     from the real ones.  There is a section on this whole topic in Reference
  628.     [1].  My general advice is to attempt to cast your model in terms of 
  629.     dollars and cents wherever possible; sometimes the multiple objectives
  630.     disappear!  8v)
  631. Q:  I have an LP that has large almost-independent matrix blocks that are
  632.     linked by a few constraints.  Can I take advantage of this?
  633. A:  In theory, yes.  See section 6.2 in Reference [1] for a discussion of 
  634.     Dantzig-Wolfe decomposition.  However, I am unaware of any commercial 
  635.     codes that will help you do this, so you'll have to create your own 
  636.     framework and then call your chosen LP solver to solve the subproblems.  
  637.     The folklore is that generally such schemes take such a long time to
  638.     converge that they're slower than just solving the model as a whole.
  639.     My advice, unless your model is so huge that a good solver can't handle 
  640.     it, is to not bother decomposing it.  (It's probably more cost effective 
  641.     to upgrade your solver, if that's why you can't solve it, than to invest 
  642.     your time.)
  643. Q:  I need to find all integer points in a polytope.
  644. A:  There is no known way of doing this efficiently.  A related question
  645.     is how to find all the vertices of an LP, with the same pessimistic
  646.     answer.  The book by Schrijver is said to discuss this.
  647. Q:  Are there any parallel LP codes?
  648. A:  IBM has announced a parallel Branch and Bound capability in their 
  649.     package OSL, for use on clusters of workstations.  "This is real, live 
  650.     commercial software, not a freebie. Contact forrest@watson.ibm.com".
  651.     Jeffrey Horn (horn@cs.wisc.edu) recently compiled a bibliography of
  652.     papers relating to research on parallel B&B.
  653.     I'm not aware of any implementations (beyond the "toy" level) of 
  654.     simplex or interior-point solvers on parallel machines.  
  655. Q:  From a roll of cloth of given width and unlimited length, cut out ...
  656. A:  You are referring to the Cutting Stock (or Trim Loss) problem.  It is 
  657.     in most LP textbooks, or Reference [1].  I think it's an interesting 
  658.     problem, because the model formulation hinges on how you generate the 
  659.     variables of the eventual LP; you can't really just write down the 
  660.     equations.  This trick of so-called Column Generation is used in diverse 
  661.     other problems such as airline crew scheduling.  A related idea, 
  662.     Constraint Generation, is used to solve the Traveling Salesman Problem.
  663. Q:  I am trying to solve a Traveling Salesman Problem ...
  664. A:  I knew you'd ask that.  Look at the bibliography in the Integer 
  665.     Programming section of Reference [1], particularly the ones with the 
  666.     names Groetschel and/or Padberg in them.  TSP is a famously hard problem 
  667.     that has attracted many of the best minds in the field.  I don't believe 
  668.     there are any commercial products to solve this problem.
  669. Q:  I heard about this new Russian algorithm for Traveling Salesman Problems.
  670. A:  You are speaking of Khachian's method for LP, published in 1979.  It was 
  671.     the first LP algorithm to have a polynomial bound on the amount of work.
  672.     Though important theoretically, it has had no impact in practice, because 
  673.     the polynomial bounds are huge.  It works by surrounding the solution 
  674.     space with a sequence of shrinking ellipsoids.  There continues to be 
  675.     research done on this method, for NLP.   The connection to TSP is false, 
  676.     brought about by an erroneous New York Times article back then.
  677. Q:  I need to do post-optimal analysis.
  678. A:  Many commercial LP codes have features to do this.  Also called Ranging
  679.     or Sensitivity Analysis, it gives you information about how much the
  680.     coefficients in the problem could change without affecting the nature
  681.     of the solution.  Most LP textbooks, such as Reference [1], describe this.
  682.  
  683. --------------------------------------------------------------------------
  684.  
  685. 9.  "Who maintains this FAQ list?"
  686.  
  687. A:  John W. Gregory
  688.     LP Specialist  (it says that on my business card, it must be true!)
  689.     Applications Department
  690.     Cray Research, Inc.
  691.     Eagan, MN 55121   USA
  692.     jwg@cray.com
  693.     612-683-3673
  694.  
  695. I suppose I should say something here to the effect that "the material
  696. in this document does not reflect any official position taken by Cray 
  697. Research, Inc."  Also, "use at your own risk", "no endorsement of products
  698. mentioned", etc., etc.  I probably should have scattered more "IMHO"s 
  699. around in the text, but that acronym seems weaselly and once you start it's 
  700. hard to know where to stop.  I should have put in a few more smilies here 
  701. and there too, to assist the humor impaired - be on your toes.  8v) 
  702.  
  703. I've tried to keep my own biases (primarily, toward the high end of 
  704. computing) from dominating what I write here, and other viewpoints that
  705. I've missed are welcome.  Suggestions, corrections, topics you'd like to 
  706. see covered, and additional material (particularly on NLP) are solicited.  
  707. Comments to the effect "who died and made *you* optimal?" will likely 
  708. result in you getting stuck with maintaining the FAQL instead of me.  8v)
  709.  
  710. I regret that when I started this list I didn't keep careful track of all 
  711. the contributors whose knowledge I tapped.  In several instances, the 
  712. information herein comes from postings on the net, which I assumed to be 
  713. fair use and in the public domain.  It being too late now to make individual 
  714. acknowledgements, I offer a blanket THANKS to all who have posted on these
  715. topics to the net.
  716.  
  717. This FAQL is also being posted to news.answers, which is archived 
  718. in the periodic posting archive on pit-manager.mit.edu [18.172.1.27],
  719. in the anonymous ftp directory /pub/usenet/news.answers.
  720.  
  721. Copies of this FAQL may be made freely, as long as it is distributed at 
  722. no charge and with this disclaimer included.
  723.  
  724. --------------------------------------------------------------------------
  725. END lp_faq
  726.